Compression techniques are widely used in computing, data storage, and electronic communications for decreasing the volume of data to allow more efficient storage and/or transmission. For example, current modem-based and DSL interconnections do not provide sufficient data transmission bandwidth to allow for transmission of uncompressed, real-time video signals at resolutions close to the resolution of broadcast television. However, highly compressed video signals can be transmitted through such internet connections and decompressed and displayed on a user's computer.
Data compression can be carried out in either a lossy or a lossless fashion. Lossy compression can generally provide much better compression ratios, but the decompressed data is generally distorted with respect to the original data. For example, in lossy compression of video signals, the decompressed video signal may have lower resolution and lower displayed frame rates. By contrast, lossless compression compresses data so that the compressed data can be accurately decompressed to identically restore the original data.
Many lossless and lossy compression methods assume a statistical model of the data being compressed. Discrepancies between the model assumed by a method and the actual statistical properties of the data result in poor compression and/or increased distortion in the reconstructed signal. Universal compression methods mitigate this problem by adapting method parameters to better suit the actual data being compressed. The various embodiments of the Lempel-Ziv compression method comprise one set of successful and widely deployed universal lossless compression methods. The Lempel-Ziv method and other lossless universal compression methods also possess certain optimality properties in a variety of formal mathematical settings involving data generated by stochastic processes and/or classes of competing data-tuned compression methods. In contrast to the lossless case, all universal lossy compression methods known to be optimal in the formal mathematical settings are hopelessly complex computationally and hence impractical. Practical universal lossy compression methods are therefore heuristically driven. Designers, developers, and users of compression methods and systems are constantly seeking new compression techniques that provide better computational efficiency and other advantages, such as improved heuristics for universal lossy compression methods.